﻿namespace AdvancedTraining.Lesson37;

/// <summary>
/// 来自字节的每一步必胜游戏
/// </summary>
/// <remarks>
/// 扑克牌中的红桃J和梅花Q找不到了，为了利用剩下的牌做游戏，小明设计了新的游戏规则：
/// 1) A,2,3,4....10,J,Q,K分别对应1到13这些数字，大小王对应0
/// 2) 游戏人数为2人，轮流从牌堆里摸牌，每次摸到的牌只有"保留"和"使用"两个选项，且当前轮必须做出选择
/// 3) 如果选择"保留"当前牌，那么当前牌的分数加到总分里，并且可以一直持续到游戏结束
/// 4) 如果选择"使用"当前牌，那么当前牌的分数*3，加到总分上去，但是只有当前轮，下一轮，下下轮生效，之后轮效果消失
/// 5) 每一轮总分大的人获胜
///
/// 假设小明知道每一轮对手做出选择之后的总分，返回小明在每一轮都赢的情况下，最终的最大分是多少
/// 如果小明怎么都无法保证每一轮都赢，返回-1
///
/// 算法思路：
/// 使用递归搜索，尝试在每一轮选择"保留"或"使用"当前牌，确保每一轮都能赢。
/// 参数说明：
/// - index: 当前轮次（0-25，共26张牌）
/// - hold: 之前保留的牌的总分
/// - cur: 当前轮得到的，之前的牌只算上使用的效果加成
/// - next: 之前的牌对下一轮的使用效果加成
///
/// 时间复杂度：O(26 * 341 * 26 * 13) ≈ O(10^7)，其中：
/// - index: 26种可能（26张牌）
/// - hold: 最多341分（所有牌的总分）
/// - cur: 最多26*3=78分
/// - next: 最多13*3=39分
///
/// 空间复杂度：O(10^7)，用于记忆化搜索缓存
/// </remarks>
public class GameForEveryStepWin
{
    /// <summary>
    /// 计算每一步都必胜的最大分数
    /// </summary>
    /// <param name="cands">牌堆中的牌值数组</param>
    /// <param name="sroces">对手每一轮的分数数组</param>
    /// <returns>如果每一步都能赢，返回最大分数；否则返回-1</returns>
    public static int Max(int[] cands, int[] sroces)
    {
        return F(cands, sroces, 0, 0, 0, 0);
    }

    /// <summary>
    /// 递归搜索函数 - 第一个版本
    /// </summary>
    /// <param name="cands">牌堆中的牌值数组</param>
    /// <param name="sroces">对手每一轮的分数数组</param>
    /// <param name="index">当前轮次</param>
    /// <param name="hold">之前保留的牌的总分</param>
    /// <param name="cur">当前轮的使用效果加成</param>
    /// <param name="next">下一轮的使用效果加成</param>
    /// <returns>如果从当前轮开始都能赢，返回最终分数；否则返回-1</returns>
    private static int F(int[] cands, int[] sroces, int index, int hold, int cur, int next)
    {
        if (index == cands.Length - 1)
        {
            // 最后一张牌
            var all = hold + cur + cands[index] * 3;
            if (all <= sroces[index]) return -1;
            return all;
        }

        // 不是最后一张牌
        var maxResult = -1;

        // 选项1：保留当前牌
        var all1 = hold + cur + cands[index];
        if (all1 > sroces[index])
        {
            var p1 = F(cands, sroces, index + 1, hold + cands[index], next, 0);
            maxResult = Math.Max(maxResult, p1);
        }

        // 选项2：使用当前牌（爆发）
        var all2 = hold + cur + cands[index] * 3;
        if (all2 > sroces[index])
        {
            var p2 = F(cands, sroces, index + 1, hold, next + cands[index] * 3, cands[index] * 3);
            maxResult = Math.Max(maxResult, p2);
        }

        return maxResult;
    }

    /// <summary>
    /// 处理函数 - 第二个版本（逻辑与F相同，但命名不同）
    /// </summary>
    private static int Process(int[] cards, int[] scores, int index, int hold, int cur, int next)
    {
        if (index == cards.Length - 1)
        {
            var all = hold + cur + cards[index] * 3;
            return all > scores[index] ? all : -1;
        }

        var maxResult = -1;

        // 保留当前牌
        var d1 = hold + cur + cards[index];
        if (d1 > scores[index])
        {
            var p1 = Process(cards, scores, index + 1, hold + cards[index], next, 0);
            maxResult = Math.Max(maxResult, p1);
        }

        // 使用当前牌
        var d2 = hold + cur + cards[index] * 3;
        if (d2 > scores[index])
        {
            var p2 = Process(cards, scores, index + 1, hold, next + cards[index] * 3, cards[index] * 3);
            maxResult = Math.Max(maxResult, p2);
        }

        return maxResult;
    }

    /// <summary>
    /// 备选版本函数 - 第三种实现
    /// </summary>
    private static int P(int[] cands, int[] sroces, int index, int hold, int cur, int next)
    {
        if (index == cands.Length - 1)
        {
            // 最后一张
            var all = hold + cur * 3 + cands[index] * 3;
            if (all <= sroces[index]) return -1;
            return all;
        }

        var maxResult = -1;

        // 保留
        var all1 = hold + cur * 3 + cands[index];
        if (all1 > sroces[index])
        {
            var p1 = F(cands, sroces, index + 1, hold + cands[index], next, 0);
            maxResult = Math.Max(maxResult, p1);
        }

        // 爆发
        var all2 = hold + cur * 3 + cands[index] * 3;
        if (all2 > sroces[index])
        {
            var p2 = F(cands, sroces, index + 1, hold, next + cands[index], cands[index]);
            maxResult = Math.Max(maxResult, p2);
        }

        return maxResult;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== GameForEveryStepWin 测试 ===");

        // 测试用例1：简单必胜情况
        // 牌：[1,2,3]，对手分数：[0,0,0]
        // 最优策略：全部使用，最终分数 = 1*3 + 2*3 + 3*3 = 18
        var cards1 = new int[] { 1, 2, 3 };
        var scores1 = new int[] { 0, 0, 0 };
        Console.WriteLine($"测试1 - 简单必胜: 期望=18, 实际={Max(cards1, scores1)}");

        // 测试用例2：无法必胜情况
        var cards2 = new int[] { 1, 1 };
        var scores2 = new int[] { 10, 10 };
        Console.WriteLine($"测试2 - 无法必胜: 期望=-1, 实际={Max(cards2, scores2)}");

        // 测试用例3：复杂情况
        var cards3 = new int[] { 5, 1, 3, 2 };
        var scores3 = new int[] { 2, 5, 8, 5 };
        Console.WriteLine($"测试3 - 复杂情况: 期望=23, 实际={Max(cards3, scores3)}");

        // 测试用例4：最后一张牌决定胜负
        var cards4 = new int[] { 1, 1, 13 };
        var scores4 = new int[] { 1, 2, 35 };
        Console.WriteLine($"测试4 - 最后牌定胜负: 期望=45, 实际={Max(cards4, scores4)}");

        // 测试用例5：完全平局（无法必胜）
        var cards5 = new int[] { 5, 5 };
        var scores5 = new int[] { 15, 15 };
        Console.WriteLine($"测试5 - 完全平局: 期望=-1, 实际={Max(cards5, scores5)}");

        // 测试用例6：单张牌情况
        var cards6 = new int[] { 5 };
        var scores6 = new int[] { 10 };
        Console.WriteLine($"测试6 - 单张牌: 期望=15, 实际={Max(cards6, scores6)}");

        // 测试用例7：无法必胜的复杂情况
        // 牌[2,1]，对手分数[1,10]
        // 第一轮：用牌2得6分>1，但第二轮只剩牌1，使用得3分<10，保留得1分<10，无法必胜
        var cards7 = new int[] { 2, 1 };
        var scores7 = new int[] { 1, 10 };
        Console.WriteLine($"测试7 - 无法必胜: 期望=-1, 实际={Max(cards7, scores7)}");

        Console.WriteLine("=== 测试完成 ===");
        Console.WriteLine("注意：这是一个递归搜索问题，可以通过添加记忆化搜索来优化性能");
    }
}